AM-GM Inequality

Theorem

The generalised AM-GM inequality states that for $x_{1}, x_{2}, \dots, x_{n} \geq 0$ :

(x_{1} \cdot \dots \cdot x_{n})^{\frac{1}{n}} \leq \frac{1}{n} \sum_{k = 1}^{n} x_{k} .

That is, the arithmetic mean is greater than or equal to the geometric mean.

Proof Using Jensen's Inequality

The AM-GM inequality can be proven quite simply by applying Jensen's inequality with $a_{i} = \frac{1}{n}$ and $f = - \ln$ . Written out explicitly this means:

- \ln (\sum_{i = 1}^{n} \frac{1}{n} x_{i}) \leq \sum_{i = 1}^{n} \frac{1}{n} (- \ln (x_{i})) .

The by negating both sides, and applying the exponential function, we have:

\begin{aligned} \ln (\sum_{i = 1}^{n} \frac{1}{n} x_{i}) \geq \sum_{i = 1}^{n} \frac{1}{n} \ln (x_{i}) \\ ⟹ \sum_{i = 1}^{n} \frac{1}{n} x_{i} \geq \exp (\sum_{i = 1}^{n} \frac{1}{n} \ln (x_{i})) \\ ⟹ \sum_{i = 1}^{n} \frac{1}{n} x_{i} \geq \exp (\sum_{i = 1}^{n} \ln (x_{i}^{\frac{1}{n}})) \\ ⟹ \sum_{i = 1}^{n} \frac{1}{n} x_{i} \geq \prod_{i = 1}^{n} x_{i}^{\frac{1}{n}} \\ ⟹ \sum_{i = 1}^{n} \frac{1}{n} x_{i} \geq {(\prod_{i = 1}^{n} x_{i})}^{\frac{1}{n}} . \end{aligned}

Proof Using Cauchy Induction

The above proof depends on the convexity $- \ln$ . It is however possible to prove it more directly without the need for this fact and Jensen's inequality. This proof uses Cauchy induction.

Base Case

We first prove a base case when $n = 2$ :

\begin{aligned} 0 & \leq (\sqrt{a} - \sqrt{b})^{2} \\ 0 & \leq a - 2 \sqrt{a b} + b \\ 2 \sqrt{a b} & \leq a + b \\ \sqrt{a b} & \leq \frac{a + b}{2} \end{aligned}

$S (n) ⟹ S (2 n)$ for $n \geq 1$

We assume that the AM-GM inequality is true for $n$ terms, and then proceed by considering the arithmetic mean of $2 n$ terms:

\begin{aligned} \frac{1}{2 n} \sum_{k = 1}^{2 n} x_{k} & = \frac{\frac{1}{n} \sum_{k = 1}^{n} x_{k} + \frac{1}{n} \sum_{k = n + 1}^{2 n} x_{k}}{2} \\ \geq \frac{{(\prod_{k = 1}^{n} x_{k})}^{\frac{1}{n}} + {(\prod_{k = n + 1}^{2 n} x_{k})}^{\frac{1}{n}}}{2} \\ \geq \sqrt{{(\prod_{k = 1}^{n} x_{k})}^{\frac{1}{n}} \cdot {(\prod_{k = n + 1}^{2 n} x_{k})}^{\frac{1}{n}}} \\ = \sqrt{{(\prod_{k = 1}^{2 n} x_{k})}^{\frac{1}{n}}} \\ = {(\prod_{k = 1}^{2 n} x_{k})}^{\frac{1}{2 n}} \end{aligned}

$S (n) ⟹ S (n - 1)$ for $n \geq 2$

Again we assume that the AM-GM inequality is true for $n$ terms. To reduce the expression to $n - 1$ terms, we let the $n^{th}$ term be the arithmetic mean of the previous $n - 1$ , that is:

x_{n} = \frac{1}{n - 1} \sum_{k = 1}^{n - 1} x_{k} .

Then we have:

\begin{aligned} {(\prod_{k = 1}^{n} x_{k})}^{\frac{1}{n}} & \leq \frac{1}{n} \sum_{k = 1}^{n} x_{k} \\ {(\prod_{k = 1}^{n - 1} x_{k})}^{\frac{1}{n}} \times {(x_{n})}^{\frac{1}{n}} & \leq \frac{1}{n} \sum_{k = 1}^{n - 1} x_{k} + \frac{1}{n} x_{n} \\ {(\prod_{k = 1}^{n - 1} x_{k})}^{\frac{1}{n}} \times {(\frac{1}{n - 1} \sum_{k = 1}^{n - 1} x_{k})}^{\frac{1}{n}} & \leq \frac{1}{n} \sum_{k = 1}^{n - 1} x_{k} + \frac{1}{n (n - 1)} \sum_{k = 1}^{n - 1} x_{k} \\ {(\prod_{k = 1}^{n - 1} x_{k})}^{\frac{1}{n}} \times {(\frac{1}{n - 1} \sum_{k = 1}^{n - 1} x_{k})}^{\frac{1}{n}} & \leq (\frac{1}{n} + \frac{1}{n (n - 1)}) \sum_{k = 1}^{n - 1} x_{k} \\ {(\prod_{k = 1}^{n - 1} x_{k})}^{\frac{1}{n}} \times {(\frac{1}{n - 1} \sum_{k = 1}^{n - 1} x_{k})}^{\frac{1}{n}} & \leq \frac{1}{n - 1} \sum_{k = 1}^{n - 1} x_{k} \\ {(\prod_{k = 1}^{n - 1} x_{k})}^{\frac{1}{n}} & \leq \frac{\frac{1}{n - 1} \sum_{k = 1}^{n - 1} x_{k}}{{(\frac{1}{n - 1} \sum_{k = 1}^{n - 1} x_{k})}^{\frac{1}{n}}} \\ {(\prod_{k = 1}^{n - 1} x_{k})}^{\frac{1}{n}} & \leq {(\frac{1}{n - 1} \sum_{k = 1}^{n - 1} x_{k})}^{\frac{n - 1}{n}} \\ {(\prod_{k = 1}^{n - 1} x_{k})}^{\frac{1}{n - 1}} & \leq \frac{1}{n - 1} \sum_{k = 1}^{n - 1} x_{k} . \end{aligned}

AM-GM Inequality

Proof Using Jensen's Inequality

Proof Using Cauchy Induction

Base Case

S(n)⟹S(2n) for n≥1

S(n)⟹S(n−1) for n≥2

$S (n) ⟹ S (2 n)$ for $n \geq 1$

$S (n) ⟹ S (n - 1)$ for $n \geq 2$